//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> dirs = {{1, 0}, {0, 1}};
int  dfs(vector<vector<int>> &grid, int row, int col,  vector<vector<int>>&memo){
    if (row == grid.size() - 1 && col == grid[0].size() - 1) {
        return grid[row][col];
    }

    if (memo[row][col] != INT_MAX) return memo[row][col];

    int minPathSum = INT_MAX;
    for (vector<int> dir : dirs) {
        int nextRow = row + dir[0];
        int nextCol = col + dir[1];
        if (nextRow < 0 || nextCol < 0
            || nextRow >= grid.size()
            || nextCol >= grid[0].size()) continue;
        int childMinPathSum = dfs(grid, nextRow, nextCol, memo);
        minPathSum = min(minPathSum, childMinPathSum);
    }
    memo[row][col] = minPathSum + grid[row][col];
    return memo[row][col];
}

int minPathSum(vector<vector<int>>& grid) {
    vector<vector<int>> memo(grid.size(), vector<int>(grid[0].size(), INT_MAX));
    return dfs(grid, 0, 0, memo);
}

//动态规划
int minPathSum1(vector<vector<int>>& grid) {
    int m  = grid.size();
    int n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n));

    //初始化状态
    dp[0][0] = grid[0][0];

    //状态转移
    for (int i = 0; i < m; i++) {//行
        for (int j = 0; j < n; j++) {//列
            if(i==0 && j!=0){
                dp[i][j] = grid[i][j]+dp[i][j-1];
            }else if (i!=0 && j==0){
                dp[i][j] = grid[i][j]+dp[i-1][j];
            }else if (i!=0 && j!=0){
                dp[i][j] = grid[i][j]+ min(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    return dp[m-1][n-1];
}

//空间压缩
// 6. 动态规划：从起始点到终点 + 状态压缩
int minPathSum4(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();

    // 状态定义：dp[i] 表示从 (0, 0) 到达第 i - 1 行的最短路径值
    vector<int> dp(n);

    // 状态初始化
    dp[0] = grid[0][0];

    // 状态转移
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j != 0) { //第一行
                dp[j] = grid[i][j] + dp[j - 1];
            } else if (i != 0 && j == 0) { // 第一列
                dp[j] = grid[i][j] + dp[j];
            } else if (i != 0 && j != 0) {
                dp[j] = grid[i][j] + min(dp[j], dp[j - 1]);
            }
        }
    }

    // 返回结果
    return dp[n - 1];
}
